﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution33
{
    public int Search2(int[] nums, int target)//想法问题
    {
        int len = nums.Length;

        if (len == 1)
        {

            if (target == nums[0])
            {

                return 0;
            }
            else
            {
                return -1;
            }

        }




        int left = 0;
        int right = len - 1;
        int mid = (left + right) / 2;

        while (left <= right)
        {

            if (target > nums[mid])//一定在右边
            {
                if (target > nums[right])
                {//在左边

                    right = mid - 1;

                }
                else if (target < nums[right])//在右边
                {
                    left = mid + 1;
                }
                else
                {
                    return right;
                }







            }
            else if (target == nums[mid])
            {
                return mid;
            }
            else
            {

                if (target > nums[left])
                {//在左边

                    right = mid - 1;

                }
                else if (target < nums[left])//在右边
                {
                    left = mid + 1;
                }
                else
                {
                    return left;
                }


            }

            mid = (left + right) / 2;

        }


        return -1;


    }
    public int Search(int[] nums, int target)//想法问题
    {
        int len = nums.Length;

        int left = 0;
        int right = len - 1;
        int mid = (left + right) / 2;

        while (left <= right)
        {
            Console.WriteLine("left:  "+ left+ "   right:  " + right);
            if (nums[left] <= nums[mid])
            //左边有序，相等的时候nums[left] == nums[mid]，说明left==mid
            //必须判断左边，否则 right = mid - 1;//left-1会越界
            //在左边target < nums[mid]，必定target < nums[left]，会变化到右边  left = mid + 1;
            {

                if (target > nums[mid])//大于左边最大得,必须右边
                {

                    left = mid + 1;


                }
                else if (target < nums[mid])
                {

                    if (target < nums[left])
                    {//右边
                        left = mid + 1;
                    }
                    else
                    {
                        right = mid - 1;//这个在nums[left] == nums[mid]的时候，不可以执行，因为left==0，会越界
                    }


                }
                else { return mid; }


            }
            else //右边有序
            {


                if (target < nums[mid])//小于右边最小得,必须左边
                {

                    right = mid - 1;


                }
                else if (target > nums[mid])
                {

                    if (target > nums[right])
                    {//左边
                        right = mid - 1;

                    }
                    else
                    {
                        left = mid + 1;
                    }


                }
                else { return mid; }
            }

            mid = (left + right ) / 2;

        }


        return -1;


    }
}

class Program33
{


    static void Main33(string[] args)
    {
        int[] nums = [3, 1];
        int target = 1;

        Solution33 solution = new Solution33();
        int res = solution.Search(nums, target);
        Console.WriteLine(res);

    }
}